# -*- coding:utf-8 -*-
from matplotlib.pyplot import *
from collections import defaultdict  
import random  
 
# function to calculate distance
def dist(p1, p2):  
  return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) ** 0.5
 
# randomly generate around 100 cartesian coordinates
all_points = []
 
for i in range(100):  
  randCoord = [random.randint(1, 50), random.randint(1, 50)]
  if randCoord not in all_points:
    all_points.append(randCoord)  
 
 
# take radius = 8 and min. points = 8
E = 8  
minPts = 8  
 
# find out the core points
other_points = []
core_points = []
plotted_points = []
for point in all_points:  
  point.append(0)         # assign initial level 0
  total = 0  
  for otherPoint in all_points:  
    distance = dist(otherPoint, point)
    if distance <= E:
      total += 1
 
  if total > minPts:  
    core_points.append(point)  
    plotted_points.append(point)  
  else:  
    other_points.append(point)  
 
# find border points
border_points = []
for core in core_points:  
  for other in other_points:  
    if dist(core, other) <= E:
      border_points.append(other)  
      plotted_points.append(other)  
 
 
# implement the algorithm
cluster_label = 0
 
for point in core_points:  
  if point[2] == 0:
    cluster_label += 1
    point[2] = cluster_label
 
  for point2 in plotted_points:  
    distance = dist(point2, point)
    if point2[2] == 0 and distance <= E:
      print(point, point2)
      point2[2] = point[2]
 
 
# after the points are asssigned correnponding labels, we group them
cluster_list = defaultdict(lambda: [[], []])
for point in plotted_points:  
  cluster_list[point[2]][0].append(point[0])  
  cluster_list[point[2]][1].append(point[1])  
 
markers = ['+', '*', '.', 'd', '^', 'v', '>', '<', 'p']
 
# plotting the clusters
i = 0
print(cluster_list)
for value in cluster_list:  
  cluster = cluster_list[value]
  plot(cluster[0], cluster[1], markers[i])
  i = i % 10 + 1
 
# plot the noise points as well
noise_points = []
for point in all_points:  
  if point not in core_points and point not in border_points:
    noise_points.append(point)  
noisex = []
noisey = []
for point in noise_points:  
  noisex.append(point[0])  
  noisey.append(point[1])  
plot(noisex, noisey, "x")  
 
title(str(len(cluster_list)) + " clusters created with E =" + str(E) + " Min Points=" + str(minPts) + " total points="
      + str(len(all_points))+" noise Points = " + str(len(noise_points)))
axis((0, 60, 0, 60))
show()
